10452. The essay
At school, Aziz was asked to write an
essay. The deadline is approaching, and Aziz still hasn't written anything. But
he knows that his friend Barysh had already completed the same task last year,
and Aziz decided to take advantage of it. However, Aziz does not want the
plagiarism detection system to be able to detect this. Therefore, Aziz decides
to write the words in all sentences of Barysh’s composition in reverse order.
After that, Aziz calculates the difference between the original proposal and
the one that he got.
Barysh’s writing consists of t sentences.
Each sentence is made up of unique words.
If the number of words in a sentence is
denoted by n, then the sentence itself can be denoted by the sequence {1,
2, ..., n}. Then the sentence corresponding to Aziz’s composition will
be denoted by the sequence {n, n – 1, ..., 1}.
The difference between the original
sentence and Aziz’s sentence is calculated as the sum of the absolute values of
the differences between the positions where the word occurs in Barysh’s sentence
and where the same word occurs in Aziz’s sentence, for all words in these
sentences. For example, in a sentence consisting of 3 words, if you
designate Barysh’s sentence as {1, 2, 3}, then Aziz’s sentence will be {3, 2, 1}
and the difference between the sentences will be |1 − 3| + |2 − 2|
+ |3 − 1| = 4.
Input. The first line contains one integer t (1 ≤
t ≤ 105) – the number of sentences in Barysh’s
composition. Each of the following t lines contains one number ni
(1 ≤ ni ≤ 109) – the number of
words in the i - th sentence.
Output. For each sentence, print on a separate line the
difference between the sentences of Barysh and Aziz.
|
Sample
input |
Sample
output |
|
3 4 3 7 |
8 4 24 |
SOLUTION
mathematics
Algorithm analysis
Let’s find a formula
– the answer to the
problem, depending on the value of the number of words n in the sentence.
Let n be
even. Consider the proposals of Barysh and Aziz:
Let’s find the sum of
numbers in the “difference” array. We divide the numbers in the array into two parts (they are the same). Let’s find the sum
of numbers from 1 to n – 1 with step 2 (arithmetic progression).
There are n / 2 numbers in this interval in total. Therefore, the sum of
all numbers in the “difference” array equals
= 
Let n be odd. Consider the
proposals of Barysh and Aziz:
Let’s find the sum of
numbers in the “difference” array. We divide the numbers in the array into two parts (they are the same). Find
the sum of numbers from 2 to n – 1 with step 2
(arithmetic progression). There are (n – 1) / 2 numbers in this interval
in total. Therefore, the sum of all numbers in the “difference” array equals
= 
= 
Example
Let n = 8.
The sum of the numbers in
the “difference” array equals 82 / 2 = 32.
Let n = 7.
The sum of the numbers in
the “difference” array equals (72 – 1) / 2 = 24.
Algorithm realization
Read the number of tests tests.
scanf("%d", &tests);
while (tests--)
{
For each value of n find and print the answer.
scanf("%d", &n);
if (n
% 2 == 0)
res = n * n / 2;
else
res = (n * n - 1) / 2;
printf("%lld\n", res);
}